package 单周赛.september;

import java.util.*;

/**
 * @
 * @date 2024/08/25
 */
public class 第412场单周赛 {

    public static void main(String[] args) {

        第412场单周赛 impl = new 第412场单周赛();

//        System.out.println(impl.countPairs(new int[]{490693, 900498, 448195, 24359, 126032, 584252, 26132, 124479, 586672, 855404, 24359, 418495, 243450, 106232, 690685, 410981, 871863, 419180, 242524, 23549, 284759, 26132, 271146, 966337, 781863, 418495, 242524, 126032, 411980, 621032, 271641, 25349, 900894, 411980, 997268, 671059, 649498, 781836, 312273, 15727, 671095}));

        System.out.println(Arrays.toString(impl.getFinalState2(new int[]{100000, 2000},
                4, 1000000)));
    }

    public int[] getFinalState(int[] nums, int k, int multiplier) {

        PriorityQueue<long[]> priorityQueue = new PriorityQueue<>((a, b) -> {
            if (a[1] - b[1] == 0) {
                return (int) (a[0] - b[0]);
            }
            return (int) (a[1] - b[1]);
        });

        for (int i = 0; i < nums.length; i++) {
            priorityQueue.add(
                    new long[]{i, nums[i]}
            );
        }
        while (k-- > 0) {
            long[] cur = priorityQueue.poll();
            cur[1] = cur[1] * multiplier % 1000000007;
            priorityQueue.add(cur);
        }

        List<long[]> list = new ArrayList<>();
        while (!priorityQueue.isEmpty()) {
            list.add(priorityQueue.poll());
        }
        list.sort((a, b) -> (int) (a[0] - b[0]));

        for (int i = 0; i < nums.length; i++) {
            nums[i] = (int) list.get(i)[1];
        }
        return nums;
    }


    public int countPairs(int[] nums) {
        int ans = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (isPair(nums[i], nums[j]) || isPair(nums[j], nums[i])) {
                    ans++;
                }
            }
        }

        return ans;
    }

    private boolean isPair(int num1, int num2) {
        if (num1 == num2) {
            return true;
        }
        char[] chars2 = (num2 + "").toCharArray();
        for (int i = 0; i < chars2.length; i++) {
            for (int j = i + 1; j < chars2.length; j++) {
                char cI = chars2[i], cJ = chars2[j];
                chars2[i] = cJ;
                chars2[j] = cI;
                if (num1 == Integer.valueOf(new String(chars2))) {
                    return true;
                }
                chars2[i] = cI;
                chars2[j] = cJ;
            }
        }

        return false;
    }


    public int[] getFinalState2(int[] nums, int k, int multiplier) {


        PriorityQueue<long[]> priorityQueue = new PriorityQueue<>((a, b) -> {
            if (a[1] - b[1] == 0) {
                return (int) (a[0] - b[0]);
            }
            return (int) (a[1] - b[1]);
        });

        for (int i = 0; i < nums.length; i++) {
            priorityQueue.add(
                    new long[]{i, nums[i]}
            );
        }
        while (k-- > 0) {
            long[] cur = priorityQueue.poll();
            cur[1] = cur[1] * multiplier;
            priorityQueue.add(cur);
        }

        List<long[]> list = new ArrayList<>();
        while (!priorityQueue.isEmpty()) {
            long[] cur = priorityQueue.poll();
            cur[1] %= 1000000007;
            list.add(cur);
        }
        list.sort((a, b) -> (int) (a[0] - b[0]));

        for (int i = 0; i < nums.length; i++) {
            nums[i] = (int) list.get(i)[1];
        }
        return nums;
    }
}
